package real.redBook;

import java.util.HashSet;

public class Ways {

    //计算对于给定的整数 n 和三个整数 a、b、c，求解从 1 到 n 的每个整数 k 可以由 a、b、c 组成的方式数

    public int[] ways(int n, int a, int b, int c){
        int[] dp = new int[n + 1];
        HashSet<Integer> set = new HashSet<>(3);
        set.add(a);
        set.add(b);
        set.add(c);
        int minab = Math.min(a,b);
        int min = Math.min(minab,c);
        for (int i = min; i <= n; i++){
            if(set.contains(i)){
                dp[i] ++;
            }
            for (Integer j : set) {
                if(j > i){
                    continue;
                }
                dp[i]  += dp[i - j];
            }
        }
        return dp;
    }
    // 测试函数
    public static void testWays() {
        Ways solution = new Ways();

        // 测试用例1: n=5, a=1, b=2, c=3
        // 1 = 1 (1种方式)
        // 2 = 1+1 or 2 (2种方式)
        // 3 = 1+1+1, 1+2, 2+1, 3 (4种方式)
        // 4 = 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 (7种方式)
        // 5 = 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2 (10种方式)
        int[] result1 = solution.ways(5, 1, 2, 3);
        System.out.println("Test 1 - n=5, a=1, b=2, c=3: " + result1);

        // 测试用例2: n=4, a=2, b=3, c=4
        // 1 = 无法组成 (0种方式)
        // 2 = 2 (1种方式)
        // 3 = 3 (1种方式)
        // 4 = 2+2, 4 (2种方式)
        int[] result2 = solution.ways(4, 2, 3, 4);
        System.out.println("Test 2 - n=4, a=2, b=3, c=4: " + result2);

        // 测试用例3: n=6, a=1, b=1, c=1 (重复情况)
        // 所有数字都可以用1组成，方式数为1
        int[] result3 = solution.ways(6, 1, 1, 1);
        System.out.println("Test 3 - n=6, a=1, b=1, c=1: " + result3);

        // 测试用例4: n=3, a=5, b=6, c=7
        // 所有1-3都无法用5,6,7组成
        int[] result4 = solution.ways(3, 5, 6, 7);
        System.out.println("Test 4 - n=3, a=5, b=6, c=7: " + result4);

        // 测试用例5: n=10, a=2, b=5, c=3
        int[] result5 = solution.ways(10, 2, 5, 3);
        System.out.println("Test 5 - n=10, a=2, b=5, c=3: " + result5);
    }

    public static void main(String[] args) {
        testWays();
    }


}
